package com.datastructure.test.worddiv;

import java.util.Arrays;
import java.util.HashSet;

public class WordDivide {

    public static void main(String[] args) {

    }

    public boolean wordDiv (String s, String[] dic) {
        // write code here
        //先移除重复字符串
        HashSet<String> set = new HashSet<>(Arrays.asList(dic));
        boolean[] dp = new boolean[s.length() + 1];//dp[i]表示s字符串中前i个字符是不是set的子集
        dp[0] = true;//空串可以被词表中的词表示
        for(int end = 1; end <= s.length(); end++){
            for(int start = 0; start < end; start++){
                if(dp[start] && set.contains(s.substring(start, end))){
                    //s[0:start]是set的子集，s[start:end]也是set的子集，所以s[0:end]是set的子集，dp[end]=true
                    dp[end] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public int getLargetLen(String[] dic) {
        int largest = Integer.MIN_VALUE;
        for (String str: dic) {
            if (str.length() > largest) {
                largest = str.length();
            }
        }
        return largest;
    }
}
